package com.tsx.leetcode.hot100.easy;

/**
 * <a href="https://leetcode.cn/problems/palindrome-linked-list">回文链表</a>
 * 1. 将后一半链表反转
 * 2. 判断前一段链表和后一段链表是不是相等判断回文
 */
public class Q234PalindromeLinkedList {
    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(2);
        ListNode l4 = new ListNode(1);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        boolean palindrome = isPalindrome(l1);
        System.out.println("palindrome = " + palindrome);
        printLinkedList(l1);
    }

    /**
     * 判断回文链表
     *
     * @param head 头节点
     * @return 是否为回文链表
     */
    public static boolean isPalindrome(ListNode head) {
        ListNode firstHalfEnd = endOfFirstHalf(head); // 获取一半链表的尾节点
        ListNode secondHalfStart = reverseList(firstHalfEnd.next); // 将后一半链表反转
        ListNode p1 = head; // 头节点
        ListNode p2 = secondHalfStart; // 后一半反转后的链表头节点
        boolean result = true; // 默认是回文
        while (result && p2 != null) { // 由于反转后的链表的尾节点next是null 所以得用p2来判断
            if (p1.val != p2.val) { // 当值不相等的时候 就不是回文
                result = false;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        firstHalfEnd.next = reverseList(secondHalfStart);
        return result;
    }

    /**
     * 利用快慢指针获取一半链表的最后一个节点
     *
     * @param head 头节点
     * @return 一半链表的最后一个节点
     */
    public static ListNode endOfFirstHalf(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 反转链表
     *
     * @param head 头节点
     * @return 反转链表后的头节点
     */
    public static ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    public static void printLinkedList(ListNode head) {
        ListNode p = head;
        while (p != null) {
            System.out.println(p.val);
            p = p.next;
        }
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}

